package dynamicStudy;

import java.util.ArrayList;
import java.util.List;

public class WordBreak {

    /**
     * LeetCode T139 单词拆分
     *
     * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
     *
     * 说明：
     *
     * 拆分时可以重复使用字典中的单词。
     * 你可以假设字典中没有重复的单词。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/word-break
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param args
     */
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        wordBreak(s, wordDict);
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        int size = wordDict.size();
        //声明状态
        int[] counts = new int[size];
        for (int i = 0; i < size; i++){
            counts[i] = wordDict.get(i).length();
        }
        int len = s.length();
        boolean[] dp = new boolean[len + 1];//默认为false
        dp[0] = true;
        //dp的索引位置
        for (int i = 1; i < len + 1; i++){
            //遍历每一个字典元素
            for (int j = 0; j < size; j++){
                if (i - counts[j] >= 0){
                    if (wordDict.get(j).equals(s.substring(i - counts[j], i)) && dp[i - counts[j]]){
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[len];
    }
}
